package algorithm.array;

/**
 * @author bingo
 * @Description       链表
 * @Date 2018/6/3
 */
public class LinkedList<E> {

    private class Node<E>{

        public E data;

        public Node next;

        public Node() {
          this(null,null);
        }

        public Node(E data) {
            this(data,null);
        }

        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }

    }
    private Node dummyHead ;

    private int size;

    public LinkedList() {
      dummyHead = new Node();
      size=0;
    }
     /**返回链表元素的个数*/
    public int getSize(){
        return  size;

    }
     /**返回链表是否为空*/
    public boolean isEmpty(){
        return  size==0;
    }
    /**增加到头节点*/
    public void addHead(E e){
       add(0,e);
    }

    public void addLast(E e){
        add(size,e);
    }
    public void add(int index,E e){
      /*  if(index==0){
            addHead(e);
            return;
         }*/
         Node prev = dummyHead;
         for(int i=0;i<index;i++){
             prev = prev.next;
        }
        Node node = new Node(e);
         node.next = prev.next;
         prev.next = node;
         size++;
    }

    public E get(int index){
        Node<E> cur = dummyHead.next;
        for(int i=0;i<index;i++){
            cur=cur.next;
        }
        return cur.data;
    }

    public E getFirst(){
        return get(0);
    }

    public E getLast(){
        return get(size-1);
    }

    public void set(int index,E e){
        Node<E> cur = dummyHead.next;
        for(int i=0;i<index;i++){
            cur=cur.next;
        }
        cur.data=e;
    }

    public boolean contain(E e){
        Node<E> cur = dummyHead.next;
        for(int i=0;i<size;i++){
            if(cur.data.equals(e)){
                return true;
            }
            cur=cur.next;
        }

             return  false;
    }

    public E remove(int index){

        Node  prev = dummyHead;
        Node<E> deleteNode = prev.next;
        for(int i=0;i<index;i++){
            prev = prev.next;
        }
        deleteNode = prev.next;
        prev.next = deleteNode.next;
        deleteNode.next=null;
        size--;
        return  deleteNode.data;
    }

    public E removeFirst(){

         return remove(0);
    }

    public E removeLast(){

        return  remove(size-1);
    }

    /**
     * 删除包含指定的元素
     * 返回头节点
     * */
    public void removeElements(E e){
        Node prev = dummyHead;
        while (prev.next!=null){
              if(prev.next.data==e){
                  Node delNode = prev.next;
                  prev.next = delNode.next;
                  }
                  else{
                   prev = prev.next;
              }
        }

    }

    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        Node node = dummyHead.next;
        while (node!=null){
            stringBuilder.append(node.data+"->");
            node = node.next;
            }
            stringBuilder.append("null");
        return  stringBuilder.toString();
    }

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        for(int i=0;i<5;i++){
            linkedList.addHead(i);
            System.out.println(linkedList.toString());
        }
        linkedList.addLast(110);
        System.out.println(linkedList.toString());
        linkedList.set(0,40);
        System.out.println(linkedList.toString());
        linkedList.addLast(70);
        linkedList.addLast(70);
        linkedList.addLast(70);
        linkedList.addHead(70);
        System.out.println(linkedList.toString());
        linkedList.removeElements(70);
        System.out.println(linkedList.toString());
        }

}

